package 数据结构.LinkList.study;

import java.util.LinkedList;
//双向循环链表
public class MyDoubleLinkedList {
    static private class Node {
        public int val;
        //记录前一个结点
        public Node pre;
        //记录后一个结点
        public Node next;

        public Node(int val) {
            this.val = val;
            this.pre = null;
            this.next = null;
        }
    }
	//记录头结点
    private Node head;
    //记录尾结点
    private Node last;
    //头插法
    public void addFirst(int val) {
        Node tmp = new Node(val);
        if (head == null) {
            head = tmp;
            last = head;
        } else {
            tmp.next = head;
            head.pre = tmp;
            head = tmp;
        }
    }
    //尾插法
    public void addLast(int val) {
        Node tmp = new Node(val);
        if (head == null) {
            head = tmp;
            last = head;
        } else {
            last.next = tmp;
            tmp.pre = last;
            last = tmp;
        }
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int val) {
        if (index < 0 || index > size()) {
            System.out.println("下标越界");
        }
        Node tmp = new Node(val);
        Node next = head;
        if(head == null){
            head = tmp;
            last = tmp;
            return;
        }
        if (index == 0) {
            tmp.next = head;
            head.pre = tmp;
            head = tmp;
            return;
        }
        if (index == size()) {
            last.next = tmp;
            tmp.pre = last;
            last = tmp;
            return;
        }
        //循环结束：表示将要让tem插入到next的位置
        while (index > 0) {
            next = next.next;
            index--;
        }
        //1-->2-->3-->4-->5[
        //           todo 如果next为3 则  next.pre=2,
        //                               next.pre.next=3
        //                               next.next=4
        //将next的前节点的后节点设置为tem
        next.pre.next = tmp;
        //将tem的后节点设置为next
        tmp.next = next;
        //todo：将tem的前节点设置为next节点的前节点
        //注意：这里的pre和next都是节点【都有节点信息】
        tmp.pre = next.pre;
        //将next的前节点设置为tmp
        next.pre = tmp;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        Node next = head;
        while (next != null) {
            if (next.val == key) {
                return true;
            }
            next = next.next;
        }
        return false;
    }

    //删除第一次出现关键字为key的节点
    public boolean remove(int key) {
        if(head == null || head.next == null){
            head = null;
            return true;
        }
        if(head.val == key){
            head = head.next;
            head.pre = null;
            return true;
        }
        Node tmp = head;
        while (tmp.val != key){
            tmp = tmp.next;
            if(tmp == null){
                return false;
            }
        }

        if(tmp == last){
            last.pre.next = null;
            return true;
        }
        tmp.pre.next = tmp.next;
        tmp.next.pre = tmp.pre;
        return true;
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        boolean b = true;
        while (b){
            b = false;
            boolean remove = remove(key);
            if(remove) b = true;
        }
    }

    //得到单链表的长度
    public int size() {
        int size = 0;
        Node next = head;
        while (next != null) {
            next = next.next;
            size++;
        }
        return size;
    }

    public void display() {
        Node next = head;
        System.out.print("[");
        while (next != null) {
            System.out.print(next.val + " ");
            next = next.next;
        }
        System.out.println("]");
    }

    public void clear() {
        while (head.next != null){
            head = head.next;
            head.pre = null;
        }
        head = null;
        last = null;
    }
}

